package com.gitee.feizns.explore.data_structure.tree.bs.easy;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author feizns
 * @since 2020/1/6
 */
public class IsCousins {

    public static void main(String[] args) {

    }

    public static boolean isCousins(TreeNode root, int x, int y) {
        Queue<N> queue = new LinkedList<>();
        queue.add(new N(root, null));
        return isCousins(queue, x, y);
    }

    private static boolean isCousins(Queue<N> queue, int x, int y) {
        Queue<N> newQueue = new LinkedList();
        N xNode = null;
        N yNode = null;
        while ( !queue.isEmpty() ) {
            N n = queue.poll();
            if ( n.node.val == x )
                xNode = n;
            else if ( n.node.val == y )
                yNode = n;
            if ( n.node.left != null )
                newQueue.add(new N(n.node.left, n.node));
            if ( n.node.right != null )
                newQueue.add(new N(n.node.right, n.node));
        }
        if ( xNode != null && yNode != null && xNode.parent != yNode.parent )
            return true;
        if ( !newQueue.isEmpty() )
            return isCousins(newQueue, x, y);
        return false;
    }

    static class N {
        TreeNode node;
        TreeNode parent;
        public N(TreeNode node, TreeNode parent) {
            this.node = node;
            this.parent = parent;
        }
    }

}
